/*
 * @lc app=leetcode.cn id=1104 lang=typescript
 *
 * [1104] 二叉树寻路
 */

// @lc code=start
function pathInZigZagTree(label: number): number[] {
  // 获取反转前的label
  const getReverse = (label: number, row: number): number => {
    // 每层的最小值
    const min = 1 << (row - 1);
    // 每层的最大值
    const max = (1 << row) - 1;
    return min + max - label;
  };

  let row = 1;
  let maxCount = 1;
  // 计算label所在的层数
  // 定义层数为i，每层的左右区间是2**(i-1)和2**i-1之间。
  while (maxCount * 2 <= label) {
    row++;
    maxCount *= 2;
  }
  // 如果label是反转后的值，将其反转成正确的值
  if (row % 2 === 0) label = getReverse(label, row);
  let ans: number[] = [];
  while (row > 0) {
    if (row % 2 === 0) {
      ans.push(getReverse(label, row));
    } else {
      ans.push(label);
    }
    row--;
    label >>= 1;
  }

  return ans.reverse();
}
// @lc code=end
